package binaryTree;

import java.util.HashMap;

class  Class105 {
//    HashMap<Integer,Integer> valToIndex=new HashMap<>();
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        if (preorder.length!=inorder.length||preorder==null&&inorder!=null||
//                preorder!=null&&inorder==null||preorder==null&&inorder==null){
//            return  null;
//        }
//        for (int i = 0; i < inorder.length; i++) {
//            valToIndex.put(inorder[i],i );
//        }
//        return  build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
//    }
//
//
//    public  TreeNode   build(int []preorder,int preStart,int preEnd,int[] inorder,int  inStart,int inEnd){
//        //递归结束条件　
//        if (preStart>preEnd){
//            return  null;
//        }
//        int rootVal=preorder[preStart];
//        Integer rootIndex = valToIndex.get(rootVal);
//        //构建根节点
//        TreeNode root = new TreeNode(rootVal);
//        int leftLeafNum=rootIndex-inStart;
//        root.left=build(preorder,preStart+1,preStart+leftLeafNum,inorder,inStart,rootIndex-1);
//        root.right=build(preorder,preStart+leftLeafNum+1,preEnd,inorder,rootIndex+1,inEnd);
//        return  root;
//    }

    HashMap<Integer,Integer> hashMap=new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length==0&&inorder.length==0||preorder.length!=inorder.length){
            return null;
        }
        for (int i = 0; i < inorder.length; i++) {
            hashMap.put(inorder[i],i );
        }

        return    build(preorder,0, preorder.length-1,inorder,0, inorder.length-1 );

    }

    public  TreeNode build(int[] preorder,int preStart,int preEnd,int[] inOrder,int inpStart,int inEnd){

//  CKG TODO 2023/4/1:  忘了考虑这个   前序序列+中序序列 构造二叉树这里判断的是 前序的start和end  如果是中序+后序 构造二叉树 那么这里判断的是 后序的start和end
        //递归结束条件　
        if (preStart>preEnd){
            return  null;
        }
        int rootVal=preorder[preStart];
        int index = hashMap.get(rootVal);
        TreeNode root = new TreeNode(rootVal);

        int leftLeafNum=index-inpStart;

        root.left=build(preorder,preStart+1,preStart+leftLeafNum,inOrder,inpStart,index-1);
        root.right=build(preorder,preStart+leftLeafNum+1,preEnd,inOrder,index+1,inEnd);
        return  root;

    }

    public static void main(String[] args) {
        Class105 class105 = new Class105();
        int [] pre={3,9,20,15,7};
        int [] in={9,3,15,20,7};
        TreeNode treeNode = class105.buildTree(pre, in);
    }


}
